#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
    struct TreeNode *parent;
    int ltag;
    int rtag;
} TreeNode;

void creatTree(TreeNode **T, char *data, int *index, TreeNode *parent) //这里parent指针可以直接传入不需要二级指针 
{                                                                      //也就是不需要修改parent直接传不同的
    char ch = data[(*index)++];
    if ('#' == ch) {
        *T = NULL;
    } else {
        (*T) = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        (*T)->parent = parent;
        (*T)->ltag = 0;
        (*T)->rtag = 0;
        creatTree(&((*T)->lchild), data, index, *T); //*T
        creatTree(&((*T)->rchild), data, index, *T);
    }
}

//和中序相同只需要改变顺序
void postThreadTree(TreeNode *T, TreeNode **pre) //二级指针全局
{
    if (T) {
        postThreadTree(T->lchild, pre);
        postThreadTree(T->rchild, pre);
        //do something 在遍历之前所以无影响
        if (T->lchild == NULL) {
            T->lchild = *pre;
            T->ltag = 1;
        }
        if (*pre != NULL && (*pre)->rchild == NULL) {
            (*pre)->rchild = T;
            (*pre)->rtag = 1;
        }
        (*pre) = T;
    }
}
// getnext()思路：
//1. 寻找最左边节点 
//2. 判断是否有右子树
//3. 如果有的话 如果没有就是这个了 
//4. 寻找最>>> (递归)

TreeNode *getFirst(TreeNode *T) //前驱ltag = 1;
{
    while (T->ltag == 0) 
        T = T->lchild; //找到最左边的节点
    if (T->rtag == 0) {//有右节点 递归
        return getFirst(T->rchild);
    }
    return T;
}

//getNext()逻辑
//为啥有这三种 左右根结束和 有左右根三种情况
//只能从现在推测之前的parent节点  此时考虑的是parent节点
//先判断 是否有右孩子 无 直接返回右孩子
//有：
//判断自身是那种情况
//1. root 返回 NULL
//2. lchild 
//       1. parent 有右孩子 getFirst(右孩子)：
//       2. parent 无右孩子 返回parent
//3. rchild 返回root
TreeNode *getNext(TreeNode *node)
{   //最后一行便于理解
    if (node->rtag == 1) {
        return node->rchild;
    }
    //是否是root
    if (node->parent == NULL) {
        return NULL;//root
    } 
    //是否是rchild
    if (node->parent->rchild == node) {
        return node->parent;
    }
    //是否是lchild
    if (node->parent->ltag == 0) {
        return getFirst(node->parent->rchild);
    }
        return node->parent;
}


void postOrder (TreeNode *T) 
{
    if (!T) return ;
    postOrder(T->lchild);
    postOrder(T->rchild);
    printf("%c ", T->data);
}

int main(void)
{
    int index = 0;
    char *data = "ABD##E##C##";
    TreeNode *T;
    TreeNode *pre = NULL;
    creatTree(&T, data, &index, NULL);
    postThreadTree(T, &pre);
    //(pre)->rchild = NULL;//最后是根节点所以省略
    //(pre)->rtag = 1;
    for (TreeNode *node = getFirst(T); node != NULL; node = getNext(node)) {
        printf("%c ", node->data);
    }    

    return 0;
}

/*
TreeNode* getNext(TreeNode* node) {
    if (node -> rtag == 1)
        return node -> rchild;
    else {
        // 如果是根节点
        if (node -> parent == NULL) {
            return NULL;
        }
            // 如果是右孩子
        else if (node -> parent -> rchild == node) {
            return node -> parent;
        }
            // 如果是左孩子
        else {
            if (node -> parent -> ltag == 0) {
                return getFirst(node -> parent -> rchild);
            }
            else {
                return node -> parent;
            }
        }
    }
}
*/